﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm
{
    public class MaxHeapSort
    {
        ///*
        // * 堆性质：如果索引从1开始，索引为i的堆父节点为i/2 ，向下取整
        // *         ，左孩子的节点为2*i,由孩子的节点为2*i +1;
        // *         
        // * 最大堆的要求A[parent(i)]>=A[i]
        // * 最小堆的要求A[parent(i)]<=A[i]
        // */

        ///// <summary>
        ///// 堆排序，原地排序，时间复杂度为 n* lgn
        ///// </summary>
        ///// <typeparam name="T"></typeparam>
        ///// <param name="array"></param>
        //public static void HeapSortArray<T>(T[] array)where T : IComparable<T>
        //{
        //    int length = array.Length;
        //    BuildMaxHeap<T>(array);

        //    for (int i = length - 1; i >= 1; i--)
        //    {
        //        Helper.Exchange<T>(array, 0, i);
        //        MaxHeapKeep<T>(array, 0, i);
        //    }
        //}

        
        ///// <summary>
        ///// 将array 建立成满足最大堆性质的
        ///// </summary>
        ///// <typeparam name="T"></typeparam>
        ///// <param name="array"></param>
        //public static void BuildMaxHeap<T>(T[] array) where T : IComparable<T>
        //{
        //    int length =array.Length;
        //    for (int i = length / 2; i >= 0; i--)
        //    {
        //        MaxHeapKeep<T>(array, i, length);
        //    }
        //}

        ////说明在建立最大堆时MaxHeapKeep 的堆大小可以设置为 数组大小，但是当排序中时，需要按照要求设置参照HeapSortArray
        ///// <summary>
        ///// 此函数确保以i为根节点的子树满足最大堆性质
        ///// </summary>
        ///// <typeparam name="T"></typeparam>
        ///// <param name="array"></param>
        ///// <param name="i"></param>
        //public static void MaxHeapKeep<T>(T[] array, int i, int heapSize) where T : IComparable<T>
        //{
        //    int length = array.Length;

        //    int leftChild = HeapLeafChild(i);
        //    int rightChild = HeapRightChild(i);

        //    int largest = i;
        //    if (leftChild < heapSize && array[leftChild].CompareTo(array[i]) > 0)
        //    {
        //        largest = leftChild;
        //    }
        //    if (rightChild < heapSize && array[rightChild].CompareTo(array[largest]) > 0)
        //    {
        //        largest = rightChild;
        //    }

        //    if (largest != i)
        //    {
        //        Helper.Exchange<T>(array, i, largest);
        //        MaxHeapKeep<T>(array, largest, heapSize);
        //    }
        //}

        //public static T MaxHeapMaximum<T>(T[] array) where T : IComparable<T>
        //{
        //    return array[0];
        //}


        ///// <summary>
        ///// 父级索引
        ///// </summary>
        ///// <param name="i"></param>
        ///// <returns></returns>
        //public static int HeapParent(int i)
        //{
        //    return (i +1) / 2 -1;//索引从1开始时 为 i/2 向下取整
        //}

        ///// <summary>
        ///// 左孩子索引
        ///// </summary>
        ///// <param name="i"></param>
        ///// <returns></returns>
        //public static int HeapLeafChild(int i)
        //{
        //    return 2 * i +1;//索引从1开始时 为 i * 2 
        //}

        ///// <summary>
        ///// 右孩子索引
        ///// </summary>
        ///// <param name="i"></param>
        ///// <returns></returns>
        //public static int HeapRightChild(int i)
        //{
        //    return 2 * i + 2;//索引从1开始时 为 i * 2 +1 
        //}
    }

    public class HeapHelper
    {
        /// <summary>
        /// 父级索引
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public static int HeapParent(int i)
        {
            return (i + 1) / 2 - 1;//索引从1开始时 为 i/2 向下取整
        }

        /// <summary>
        /// 左孩子索引
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public static int HeapLeafChild(int i)
        {
            return 2 * i + 1;//索引从1开始时 为 i * 2 
        }

        /// <summary>
        /// 右孩子索引
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public static int HeapRightChild(int i)
        {
            return 2 * i + 2;//索引从1开始时 为 i * 2 +1 
        }
    }

    public class MaxHeapSort<T> where T : IComparable<T>
    {
        private T[] _data;
        public MaxHeapSort(T[] data)
        {
            this._data = data;
            this.ArraySize = data.Length;
            this.HeapSize = data.Length ;
            BuildMaxHeap(data);
        }

        public int HeapSize
        {
            get;
            private set;
        }

        public int ArraySize
        {
            get;
            private set;
        }

        /// <summary>
        /// 将array 建立成满足最大堆性质的
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        private void BuildMaxHeap(T[] array) 
        {
            int length = array.Length;
            for (int i = length / 2; i >= 0; i--)
            {
                MaxHeapKeep(array, i);
            }
        }

        //说明在建立最大堆时MaxHeapKeep 的堆大小可以设置为 数组大小，但是当排序中时，需要按照要求设置参照HeapSortArray
        /// <summary>
        /// 此函数确保以i为根节点的子树满足最大堆性质
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        /// <param name="i"></param>
        private void MaxHeapKeep(T[] array, int i) 
        {
            int length = array.Length;

            int leftChild = HeapHelper.HeapLeafChild(i);
            int rightChild = HeapHelper.HeapRightChild(i);

            int largest = i;
            if (leftChild < this.HeapSize && array[leftChild].CompareTo(array[i]) > 0)
            {
                largest = leftChild;
            }
            if (rightChild < this.HeapSize && array[rightChild].CompareTo(array[largest]) > 0)
            {
                largest = rightChild;
            }

            if (largest != i)
            {
                Helper.Exchange<T>(array, i, largest);
                MaxHeapKeep(array, largest);
            }
        }

        public T MaxHeap_Maximum()
        {
            return this._data[0];
        }

        public T MaxHeap_Extract_Max()
        {
            if (this.HeapSize < 1)
            {
                throw new Exception("Empty");
            }
            T result = this._data[0];

            this._data[0] = this._data[--this.HeapSize];

            MaxHeapKeep(this._data, 0);

            return result;
        }

        public void MaxHeap_Increase_key(int i, T key)
        {
            if (key.CompareTo(this._data[i]) < 0)
            {
                throw new Exception("can not do it");
            }
        
            this._data[i] = key;
            while (i > 0 && this._data[HeapHelper.HeapParent(i)].CompareTo(this._data[i]) < 0)
            {
                Helper.Exchange<T>(this._data, i, HeapHelper.HeapParent(i));
                i = HeapHelper.HeapParent(i);
            }
        }

        public void MaxHeap_Insert(T key, T min)
        {

            if (this.HeapSize == this.ArraySize)
            {
                this.ArraySize = 2 * this.ArraySize;
                T[] newdata = new T[this.ArraySize];
                Array.Copy(this._data, newdata, this.ArraySize);
                this._data = newdata;
            }
            this._data[this.HeapSize++] = min;
            MaxHeap_Increase_key(this.HeapSize-1, key);
        }

        /// <summary>
        /// 堆排序，原地排序，时间复杂度为 n* lgn,多线程会出问题。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        public T[] HeapSortArray()
        {
            T[] tmp = new T[this._data.Length];
            var oldHeap = this.HeapSize;
            for (int i = 0; i < this._data.Length; i++)
            {
                tmp[i] = this._data[i];
            }

            for (int i = tmp.Length - 1; i >= 1; i--)
            {
                Helper.Exchange<T>(tmp, 0, i);
                this.HeapSize--;
                MaxHeapKeep(tmp, 0);
            }
            this.HeapSize = oldHeap;
            return tmp;
        } 
    }

    public class MinHeapSort<T> where T : IComparable<T>
    {
         private T[] _data;
         public MinHeapSort(T[] data)
        {
            this._data = data;
            this.ArraySize = data.Length;
            this.HeapSize = data.Length ;
            BuildMinHeap(data);
        }

        public int HeapSize
        {
            get;
            private set;
        }

        public int ArraySize
        {
            get;
            private set;
        }

        /// <summary>
        /// 将array 建立成满足最大堆性质的
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        private void BuildMinHeap(T[] array) 
        {
            int length = array.Length;
            for (int i = length / 2; i >= 0; i--)
            {
                MinHeapKeep(array, i);
            }
        }

        //说明在建立最大堆时MaxHeapKeep 的堆大小可以设置为 数组大小，但是当排序中时，需要按照要求设置参照HeapSortArray
        /// <summary>
        /// 此函数确保以i为根节点的子树满足最大堆性质
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        /// <param name="i"></param>
        private void MinHeapKeep(T[] array, int i) 
        {
            int length = array.Length;

            int leftChild = HeapHelper.HeapLeafChild(i);
            int rightChild = HeapHelper.HeapRightChild(i);

            int largest = i;
            if (leftChild < this.HeapSize && array[leftChild].CompareTo(array[i]) < 0)
            {
                largest = leftChild;
            }
            if (rightChild < this.HeapSize && array[rightChild].CompareTo(array[largest]) < 0)
            {
                largest = rightChild;
            }

            if (largest != i)
            {
                Helper.Exchange<T>(array, i, largest);
                MinHeapKeep(array, largest);
            }
        }

        public T MinHeap_Minimum()
        {
            return this._data[0];
        }

        public T MinHeap_Extract_Min()
        {
            if (this.HeapSize < 1)
            {
                throw new Exception("Empty");
            }
            T result = this._data[0];

            this._data[0] = this._data[--this.HeapSize];

            MinHeapKeep(this._data, 0);

            return result;
        }

        public void MinHeap_DeIncrease_key(int i, T key)
        {
            if (key.CompareTo(this._data[i]) > 0)
            {
                throw new Exception("can not do it");
            }
        
            this._data[i] = key;
            while (i > 0 && this._data[HeapHelper.HeapParent(i)].CompareTo(this._data[i]) > 0)
            {
                Helper.Exchange<T>(this._data, i, HeapHelper.HeapParent(i));
                i = HeapHelper.HeapParent(i);
            }
        }

        public void MinHeap_Insert(T key, T max)
        {

            if (this.HeapSize == this.ArraySize)
            {
                this.ArraySize = 2 * this.ArraySize;
                T[] newdata = new T[this.ArraySize];
                Array.Copy(this._data, newdata, this.ArraySize);
                this._data = newdata;
            }
            this._data[this.HeapSize++] = max;
            MinHeap_DeIncrease_key(this.HeapSize - 1, key);
        }

        /// <summary>
        /// 堆排序，原地排序，时间复杂度为 n* lgn,多线程会出问题。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        public T[] HeapSortArray()
        {
            T[] tmp = new T[this._data.Length];
            var oldHeap = this.HeapSize;
            for (int i = 0; i < this._data.Length; i++)
            {
                tmp[i] = this._data[i];
            }

            for (int i = tmp.Length - 1; i >= 1; i--)
            {
                Helper.Exchange<T>(tmp, 0, i);
                this.HeapSize--;
                MinHeapKeep(tmp, 0);
            }
            this.HeapSize = oldHeap;
            return tmp;
        } 
    }
}
